0179. 最大数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 自定义排序

1. 📝 题目描述

• leetcode

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

---

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

---

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

---

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

2. 🎯 s.1 - 自定义排序

c

int cmp(const void* a, const void* b) {
    char ab[24], ba[24];
    sprintf(ab, "%s%s", *(char**)b, *(char**)a);
    sprintf(ba, "%s%s", *(char**)a, *(char**)b);
    return strcmp(ab, ba);
}

char* largestNumber(int* nums, int numsSize) {
    char** strs = (char**)malloc(sizeof(char*) * numsSize);
    for (int i = 0; i < numsSize; i++) {
        strs[i] = (char*)malloc(12);
        sprintf(strs[i], "%d", nums[i]);
    }
    qsort(strs, numsSize, sizeof(char*), cmp);
    if (strs[0][0] == '0') {
        for (int i = 0; i < numsSize; i++) free(strs[i]);
        free(strs);
        char* res = (char*)malloc(2);
        res[0] = '0'; res[1] = '\0';
        return res;
    }
    int totalLen = 0;
    for (int i = 0; i < numsSize; i++) totalLen += strlen(strs[i]);
    char* res = (char*)malloc(totalLen + 1);
    res[0] = '\0';
    for (int i = 0; i < numsSize; i++) {
        strcat(res, strs[i]);
        free(strs[i]);
    }
    free(strs);
    return res;
}

js

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function (nums) {
  const strs = nums.map(String)
  strs.sort((a, b) => (b + a).localeCompare(a + b))
  if (strs[0] === '0') return '0'
  return strs.join('')
}

py

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        from functools import cmp_to_key
        strs = list(map(str, nums))
        strs.sort(key=cmp_to_key(lambda a, b: (1 if a + b < b + a else -1 if a + b > b + a else 0)))
        res = ''.join(strs)
        return '0' if res[0] == '0' else res

• 时间复杂度：$O(n\log n)$，其中 $n$ 是数组长度
• 空间复杂度：$O(n)$，存储字符串数组

算法思路：

• 将数字转为字符串，自定义比较器：比较 a + b 和 b + a 的字典序
• 例如比较 "3" 和 "30"："330" > "303"，所以 "3" 排在 "30" 前面
• 特殊情况：排序后若首位为 '0'，说明所有数字都是 0，直接返回 "0"